Chapter 3 -- Graph ( 3 )

發表於 2019-10-24 更新於 2019-11-02 分類於課程筆記 Course ，江蕙如 Algorithm 閱讀次數： 74 Disqus：

Application of BFS -- Testing Bipartiteness

Definition

The nodes of graph can be partitioned into two sets $X$ and $Y$ and one every edge has one end in $X$ and the other end in $Y$ .We call it bipartite graph ( bigraph ) . 一個 graph 的 nodes 可以分成兩個集合，且每一條 edge 兩端連接的端點均屬不同集合者稱之為 bipartite graph ( bigraph ) 。

從此定義我們可以推得兩個 bipartite graph 性質

$X \cap Y = ϕ$
$\forall x_{1}, x_{2} \in X ⟹ x_{1} i s n^{'} t t h e n e i g h b o r o f x_{2} ⟹ ∄ e d g e b e t w e e n x_{1} a n d x_{2}$

了解其定義後，我們要問的問題是，給定一個 graph，我們如何判定是否為 bipartite graph ? 直覺一點的方式就是直接將每一個 edge 的兩個端點塗上兩個不同的顏色，然後看看是否會有衝突的地方。

如果寫成 procedure 的話 (假設 $G$ 是 connected graph以簡化運算)

1. 先任選一點 s∈V,並且將其著色成紅色
2. 對它的所有 neighbors 著色成藍色
3. 重複對 neighbors 塗 紅/藍 色直至所有點都被著色完成
4. 若為 bipartite graph 則所有 edges 的兩端都為不同顏色

這個 procedure 要 implement 其實就是用 BFS，只是在 BFS procedure 中每一個 layer 再多加一個著色的動作即可。

[ 補充 ]

實際上，有一個定理可以幫助我們更方便來做判定 :

$G r a p h G i s b i p a r t i t e, i f a n d o n l y i f i t d o e s n^{'} t h a v e a n y o d d c y c l e .$ 如果 $G$ 是一個 bipartite graph，則不存在奇數 circle。也就是說， $G$ 裡面的每一個 circle，都是由偶數條 edges 所構成。

Claim : $G i s a c o n n e c t e d g r a p h a n d L_{0}, L_{1}, \dots a r e t h e l a y e r s p r o d u c e d b y B F S s t a r t i n g a t n o d e s$ 1. $T h e r e i s n o e d g e o f G j o i n s t w o n o d e s o f t h e s a m e l a y e r ⟺ i f G i s b i p a r t i t e .$ 2. $T h e r e i s a n e d g e o f G j o i n s t w o n o d e s o f t h e s a m e l a y e r ⟺ G c o n t a i n s a n o d d - l e n g t h c y c l e .$

Proof :

(2. $⟹$ ) 假設在第 $L_{j}$ 層有一條 edge 相連兩個 nodes $x, y$ ，由於 BFS 均可以 tree 的型態表示，此兩點 $x, y$ 與原點 $s$ 之間必然各自存在一條 path，且這兩條 paths 會在某一層 $L_{i}$ 中某一點 $z$ 交會。

從上圖可以知道 $x, y, z$ 三個 nodes 會形成一個 cycle，其 length $= 1 + 2 \times (j - i)$ $∴ x, y, z$ 三個 nodes 會形成一個 odd cycle $⟹$ G is not a bipartite graph

(2. $⟸$ ) Clearly by definition.

(1.) Clearly by 2.

Connectivity in directed graphs

Definition

Nodes $u, v$ are mutually reachable if $\exists$ a path from $u$ to $v$ and also $\exists$ a path from $v$ to $u$ 若兩點間互相存在一條 path 可以從一點到另一點，則稱之為 mutmally reachable。
A directed graph is strongly connected if $\forall$ pairs of nodes are mutually reachable. 一個有向圖若任兩點均為 mutually reachable，則稱其為 stronglly connected。
The strongly (connected) component $S$ containing $s$ in a directed graph is the maximal set if $\forall v \in S$ s.t. $v$ and $s$ are mutually reachable. 所有和 $s$ 為 mutually reachable 的 nodes 形成一個 strongly component。

Lemma

$I f u a n d v a r e m u t u a l l y r e a c h a b l e, a n d v a n d w a r e m u t u a l l y r e a c h a b l e, t h e n u a n d w a r e m u t u a l l y r e a c h a b l e .$

Testing strongly connectivity

如果給定一個 directed graph ，我們可以如何檢查它是否為 strongly connected ? 最直覺也是最笨的方式就是做兩次 BFS，第一次先檢查 $s$ 可以到達的點有哪些，第二次再檢查這些點能不能回到 $s$ 。

然而這樣的複雜度太高，因此稍微調整一下。

TestStronglyConnectivity(G):

1. 選擇任一點作為起始點 s
2. R=BFS(s,G)  
#針對此起始點對 G 做BFS
3. R'=BFS(s,G') where G' = the graph that it's edges are reverse direction of all edges of G
#製造一個方向與 G 完全相反的有向圖 G'，並做一次 BFS
4. 若 R=V=R'，則 return true else false

這裡每一個步驟都是 linear time complexity，最後的總時間複雜度為 $O (m + n)$

關於 strongly (connected) component 有一些蠻有趣的性質

任一個 directed graph 必可以拆出數個 strongly (connected) component。
將 directed graph 的所有 strongly (connected) component 都各自視為一個點，那麼必會形成一個 directed acyclic graph。

Theorem

$F o r a n y t w o n o d e s s a n d t i n a d i r e c t e d g r a p h, t h e i r s t r o n g l y c o m p o n e n t a r e i d e n t i c a l o r d i s j o i n t .$ 在一個有向圖中任取兩個 nodes，這兩個 nodes 必在相同的 Strongly Component 不然就各在互斥的兩個 strongly component 中。

Proof :

( Case 1. ) $s$ and $t$ are mutually reachable.

Clearly be definition.

( Case 2. ) $s$ and $t$ are not mutually reachable.

Suppose to the contrary that $\exists v$ s.t. $s$ and $v$ are mutually reachable and $t$ and $v$ are mutually reachable

$⟹$ $s$ and $t$ are mutually reachable. ( $\to\leftarrow$ )